#pragma once
#include "SHash.h"
#include "../strings/BaseString.h"
#include <unordered_map>

namespace qb{
namespace base{
	template<class KEY>
	class DefaultHash{
	public:
		unsigned int operator()(const KEY& k)const{
			return GetFastHash(&k, sizeof(KEY), 0);
		}
	};

	template<>
	class DefaultHash<std::string>{
	public:
		unsigned int operator()(const std::string& k)const{
			return GetFastHash(k.c_str(), k.size(), 0);
		}
	};
	template<>
	class DefaultHash<BaseString>{
	public:
		unsigned int operator()(const BaseString& k)const{
			return GetFastHash(k.c_str(), k.size(), 0);
		}
	};

	template<class KEY, class VALUE,class HASHER=DefaultHash<KEY>>
class CHashMap
{
	typedef unsigned int HashCode;
	typedef CHashMap<KEY, VALUE,HASHER> ThisType;
public:
	class iterator;
private:
	class Entry{
		friend class iterator;
		unsigned int		m_hash;		// 哈希值
		KEY					m_key;		// 容纳的键
		VALUE				m_value;	// 容纳的值
		Entry*				m_next;		// 单链表
	private:
		Entry(){}
		Entry(const Entry& et){}
		Entry& operator=(const Entry& et)const{ return *this; }
	public:
		Entry(unsigned int nHash,const KEY& k,const VALUE& v):m_hash(nHash),m_key(k),m_value(v),m_next(NULL){}
		bool update(const KEY& k,const VALUE& v)
		{
			Entry* cur = this;
			do 
			{
				if (cur->m_key == k){ cur->m_value = v; return true; }
				cur = cur->m_next;
			} while (cur);
			return false;
		}
		bool find(const KEY& k,VALUE& v)const
		{
			const Entry* cur = this;
			do
			{
				if (cur->m_key == k){
					v=cur->m_value; 
					return true; 
				}
				cur = cur->m_next;
			} while (cur);
			return false;
		}
		unsigned int gethash()const{
			if (m_hash == 0){(const_cast<Entry*>(this))->m_hash = HASHER()(m_key);}
			return m_hash;
		}
		bool equalwith(unsigned int nhash, const KEY& k)const{ return nhash == m_hash && m_key == k; }
		Entry* getnext()const{ return m_next; }
		void setnext(Entry* next){ m_next = next; }
		const VALUE& getvalue()const{ return m_value; }
	};
	struct EntrySlot{
		Entry*	head;
		int		count;
	};
	//Entry**					m_buckets;		// 插槽+单链表
	EntrySlot*				m_buckets;
	int						m_capcity;		// 插槽个数
	int						m_expand_size;	// 超过此值,表示需要扩张
	int						m_count;		// 实际容纳的个数
	int						m_max_len;		// 历史上的最大长度,仅供参考
public:
	CHashMap(int size=1024):
		m_capcity(size),
		m_expand_size(size),
		m_count(0),
		m_max_len(0)
	{
		m_buckets = new EntrySlot[m_capcity];
		memset(m_buckets, 0, sizeof(EntrySlot)*m_capcity);
	}
	~CHashMap()
	{
		Clear();
		if (m_buckets)
			delete [] m_buckets;
		m_buckets = nullptr;
	}
	void SetExpandRatio(double ratio)
	{
		ratio = ratio <= 1.0 ? 1.0 : ratio;
		m_expand_size = m_capcity*ratio;
	}
	double GetExpandRatio()const{ return m_capcity <= 0 ? 0 : (m_expand_size*1.0 / m_capcity); }
	double GetLoadFactor()const{return m_capcity <= 0 ? 0 : (m_count*1.0 / m_capcity);}
	int GetMaxSlotLength()const{ return m_max_len; }
	void Clear()
	{
		int ncount = 0;
		for (int i=0;i<m_capcity;i++)
		{
			Entry* entry = m_buckets[i].head;
			ncount += m_buckets[i].count;
			while (entry)
			{
				Entry* temp = entry;
				entry = entry->getnext();
				delete temp;
			}
		}
		//BASSERT(m_count == ncount);
		m_count  = 0;
		memset(m_buckets,0,sizeof(EntrySlot)*m_capcity);
	}

	// use default hash function:GetFastHash
	bool Insert(const KEY& k,const VALUE& v)
	{
		unsigned int nhash = HASHER()(k);
		return Insert(k,nhash,v);
	}
	bool Find(const KEY& k,VALUE& v)const
	{
		unsigned int nhash = HASHER()(k);
		int ipos = nhash%m_capcity;
		Entry* entry = m_buckets[ipos].head;
		return entry ? entry->find(k, v) : false;
	}

	bool Erase(const KEY& k, VALUE& v)
	{
		unsigned int nhash = HASHER()(k);
		int ipos = nhash%m_capcity;
		Entry* prev = nullptr;
		EntrySlot& slot = m_buckets[ipos];
		Entry* entry = slot.head;
		while (entry)
		{
			if (entry->equalwith(nhash, k))
			{
				if (prev == nullptr)
					slot.head = entry->getnext();
				else
					prev->setnext(entry->getnext());
				entry->setnext(nullptr);
				v = entry->getvalue();
				delete entry;
				m_count--;
				slot.count--;
				BASSERT(m_count >= 0 && slot.count >= 0);
				return true;
			}
			prev = entry;
			entry = entry->getnext();
		}
		return true;
	}

	// leave hash function to caller
	bool Insert(const KEY& k,unsigned int nhash,const VALUE& v)
	{
		int ipos = nhash%m_capcity;
		EntrySlot& slot = m_buckets[ipos];
		Entry* entry = slot.head;
		if(entry && entry->update(k,v))
		{
			return true;
		}
		entry = new Entry(nhash,k,v);
		entry->setnext(slot.head);
		slot.head = entry;
		slot.count++;
		m_count ++;
		SetMaxSlotLen(slot.count);
		if (m_count > m_expand_size)
		{
			Expand(m_count<1024 ? m_count * 8 : m_count * 2);
		}
		return true;
	}
	bool Find(const KEY& k,unsigned int nhash,VALUE& v)const
	{
		int ipos = nhash%m_capcity;
		Entry* entry = m_buckets[ipos].head;
		return entry?entry->find(k,v):false;
	}
	int Count()const{ return m_count; }
	int Capcity()const{ return m_capcity; }
	int Bytes()const{
		return m_capcity*sizeof(EntrySlot) + m_count*sizeof(Entry) + sizeof(*this);
	}
	void Expand(int ncount)
	{
		if (ncount <= m_capcity)return;
		ThisType temp(ncount);
		//printf("\ncapcity:%8d count:%8d==>%8d  max_slot_len:%8d", m_capcity, m_count, ncount, m_max_len);
		for (int i = 0; i < m_capcity; i++)
		{
			Entry* first = m_buckets[i].head;
			while (first)
			{
				Entry* next = first->getnext();
				first->setnext(0);
				temp.InsertImpl(first);
				first = next;
			}
			m_buckets[i].head = nullptr;
			m_buckets[i].count = 0;
		}
		m_count = 0;
		Swap(temp);
	}
	class iterator{
		const CHashMap*	m_hashmap;
		Entry*		m_current;
		bool		m_reverse;
		friend class CHashMap;
	protected:
		iterator(const CHashMap* hashmap,Entry* cur,bool reverse):m_hashmap(hashmap),m_current(cur),m_reverse(reverse){}
	public:
		iterator& operator=(const iterator& it);
		iterator(const iterator& it);
		iterator& operator++(){m_current=m_hashmap->NextEntry(m_current);return *this;}
		bool operator==(const iterator& other){return m_hashmap==other.m_hashmap && m_reverse==other.m_reverse && m_current==other.m_current;}
		bool operator!=(const iterator& other){
			return m_hashmap!=other.m_hashmap 
				|| m_reverse!=other.m_reverse || m_current!=other.m_current;}
		const KEY& first(){return m_current->m_key;}
		const VALUE& second()const{return m_current->m_value;}
		//VALUE& second(){ return m_current->m_value; }
		operator bool(){return m_current!=0;}
	};

	iterator begin()const{return iterator(this,FirstEntry(),false);}
	iterator end()const{return iterator(this,0,false);}
protected:
	inline void SetMaxSlotLen(int slotLength)
	{
		m_max_len = m_max_len < slotLength ? slotLength : m_max_len;
	}
	void Swap(ThisType& otherMap)
	{
		std::swap(m_buckets, otherMap.m_buckets);
		std::swap(m_capcity, otherMap.m_capcity);
		std::swap(m_count, otherMap.m_count);
		std::swap(m_max_len, otherMap.m_max_len);
		std::swap(m_expand_size, otherMap.m_expand_size);
	}
	bool InsertImpl(Entry* entry)
	{
		unsigned int nhash = entry->gethash();
		EntrySlot& slot = m_buckets[nhash%m_capcity];
		entry->setnext(slot.head);
		slot.head = entry;
		slot.count++;
		m_count++;
		SetMaxSlotLen(slot.count);
		return true;
	}
	Entry* FirstEntry()const{
		if(m_buckets)
		{
			for (int i=0;i<m_capcity;i++)
			{
				if (m_buckets[i].head != nullptr)
				{
            //		BASSERT(m_buckets[i].count > 0);
					return m_buckets[i].head;
				}
			}
		}
		return 0;
	}
	Entry* NextEntry(Entry* entry)const
	{
		if(m_buckets && entry )
		{
			int slot = entry->gethash()%m_capcity;
			if(entry->getnext())
				return entry->getnext();
			for (int i=slot+1;i<m_capcity;i++)
			{
				if (m_buckets[i].head != nullptr)
				{
                //	BASSERT(m_buckets[i].count > 0);
					return m_buckets[i].head;
				}
			}
		}
		return 0;
	}
};

template<class KEY, class VALUE,int SLOT=512,int CAPCITY=1024, class HASHER = DefaultHash<KEY>>
class CStackHashMap{
	typedef std::unordered_map<KEY, VALUE, HASHER> HeapHashMap;
	typedef unsigned int uint;
	struct Item{
		uint	hash;
		KEY		key;
		VALUE	val;
		Item*	next;
	};
	int				m_count;			// m_items中使用的个数
	int				m_slot;				// 哈希插槽的个数
	int				m_capcity;			// 栈上最多能允许多少个记录
	HeapHashMap*	m_heapmap;			// 超过CAPCITY之后,使用标准哈希表
	Item*			m_slots[SLOT];		// 哈希插槽指针
	Item			m_items[CAPCITY];	// 额定的CAPCITY个Item对象,在栈上
public:
	CStackHashMap() :m_count(0), m_heapmap(nullptr), m_slot(SLOT), m_capcity(CAPCITY){
		memset(m_slots, 0, SLOT*sizeof(Item*));
		memset(m_items, 0, CAPCITY*sizeof(Item));
	}
	~CStackHashMap(){if (m_heapmap)delete m_heapmap;}
	bool Insert(const KEY& k, const VALUE& v)
	{
		if (m_heapmap)
		{
			m_heapmap->operator[](k)= v;
			return true;
		}
		uint nhash = HASHER()(k);
		int ipos = nhash%m_slot;
		for (Item* it = m_slots[ipos]; it != nullptr; it = it->next)
		{
			if (it->hash == nhash && it->key == k)
			{
				it->val = v;
				return true;
			}
		}
		if (m_count >= m_capcity)
		{
			Expand();
            auto it = m_heapmap->insert(typename HeapHashMap::value_type(k, v));
			return it.second;
		}
		Item* item = &m_items[m_count++];
		item->key = k;
		item->val = v;
		item->hash = nhash;
		item->next = m_slots[ipos];
		m_slots[ipos]= item;
		return true;
	}
	bool Exist(const KEY& k)const
	{
		if (m_heapmap)
		{
			auto it = m_heapmap->find(k);
			return it != m_heapmap->end();
		}
		uint nhash = HASHER()(k);
		int ipos = nhash%m_slot;
		for (Item* it = m_slots[ipos]; it != nullptr; it = it->next)
		{
			if (it->hash == nhash && it->key == k)
				return true;
		}
		return false;
	}
	bool Find(const KEY& k, VALUE& v)const
	{
		if (m_heapmap)
		{
			auto it = m_heapmap->find(k);
			if (it != m_heapmap->end())
			{
				v = it->second;
				return true;
			}
			return false;
		}
		uint nhash = HASHER()(k);
		int ipos = nhash%m_slot;
		for (Item* it = m_slots[ipos]; it != nullptr; it = it->next)
		{
			if (it->hash == nhash && it->key == k)
				return true;
		}
		return false;
	}
	bool Update(const KEY& k, const VALUE& v)
	{
		// 如果没有key,那么更新失败,返回false
		// 效果等同于
		// if(Exist(k))continue;
		// Insert(k,v);
		if (m_heapmap)
		{
            auto it=m_heapmap->insert(typename HeapHashMap::value_type(k, v));
			return it.second;
		}
		uint nhash = HASHER()(k);
		int ipos = nhash%m_slot;
		for (Item* it = m_slots[ipos]; it != nullptr; it = it->next)
		{
			if (it->hash == nhash && it->key == k)
				return false;
		}
		if (m_count >= m_capcity)
		{
			Expand();
            auto it = m_heapmap->insert(typename HeapHashMap::value_type(k, v));
			return it.second;
		}

		Item* item = &m_items[m_count++];
		item->key = k;
		item->val = v;
		item->hash = nhash;
		item->next = m_slots[ipos];
		m_slots[ipos] = item;
		return true;
	}
	int Size()const{ return m_heapmap ? m_heapmap->size() : m_count; }
protected:
	void Expand()
	{
		m_heapmap = new HeapHashMap();
		for (int i = 0; i < m_count; i++)
		{
			Item& it = m_items[i];
			m_heapmap->operator[](it.key) = it.val;
		}
	}
};
//#ifdef SSBASE_EXPORTS
//#include "CHashMap.hpp"
//#endif

}//namespace base;
}//namespace ss;
